This invention relates generally to hardware interfaces between communication stations and various types of transmission media used in communication networks, particularly high-speed token ring networks such as the Fiber Data Distributed Interface (FDDI) token ring system.
A network adapter is an interface device that is located between a communication network and an input-output (I-O) bus of a workstation to be connected to the network. Data packets flow through the adapter in both directions, and the adapter has two broad functions to perform. It has to make sure that packets do not get lost, or at least that not too many get lost, and it has to make sure that progress is made in processing traffic received from the network or to be transmitted onto the network. In relatively high-speed networks, such as the Fiber Data Distributed Interface (FDDI) token ring system, the network adapter often has its own processor to handle these functions. The present invention is concerned with relatively low cost adapters, in which no transmit traffic (toward the network) is handled by the adapter processor. In this situation, the adapter has two basic tasks to perform: processing packets received from the network and delivering them to a host processor in a timely manner, and performing background tasks for the FDDI system.
Conventionally, adapters have used scheduling mechanisms that are "interrupt driven," which means that, when a packet is received by the adapter, ongoing processing is interrupted to handle the incoming packet. The use of interrupts for scheduling operations of a network adapter is a convenient technique for several reasons. First, each processing function can be developed independently and "compartmentalized" for testing and subsequent modification. Interrupts allow for a clean division of the functions, and each function can be asynchronously invoked as the need arises. Theoretically, an interrupt driven scheduling approach could also allow for a timely invocation of the functions. But if the interrupt processing overhead becomes too great compared with the remainder of work performed for tasks invoked by interrupts, the latency for completing the functions can be excessive. In other words the interrupt processing overhead can be a large percentage of the total processing load.
In general, network adapter functions include: "receive processing," to handle the movement of data received from the network, "transmit processing," to handle the movement of data to be transmitted onto the network, timer driven background tasks, background management tasks, background command processing (initiated by a host processor), and processing exception conditions. The background host command processing tasks are for such functions as initialization and FDDI management. The background management tasks fall into various categories: station management tasks relating to frame processing (involving messages that help keep the token ring network operational), and ring management and connection management tasks. In the context of the present invention, we are concerned with all types of processing except transmit processing, and the specific nature of the background tasks is not important.
Interrupt driven scheduling mechanisms have two significant disadvantages. One is that they necessarily involve additional latency before received information is made available to a program specific to receive processing that will ultimately process the information. Interrupt driven scheduling mechanisms typically have an "idle loop" that is executed by the adapter while waiting for an interrupt. The interrupt takes the adapter out of its idle loop and into an interrupt service routine, which in turn invokes a processing routine to handle the received packet. Delay occurs in saving the "context" in which the interrupt occurred, i.e. saving register values and other critical information. The saving of these registers is desirable so that the interrupt service routine may use the registers to process received packets more efficiently. The latency involved in these operations interposes a significant delay in the processing of received packets. Some applications are more sensitive to this latency than others, but the latency is significant in many cases.
The other major disadvantage of interrupt driven scheduling mechanisms is that the high priority afforded to the processing of received packets may repeatedly deny processing time to background tasks awaiting completion. In heavy traffic situations, it may be impossible to guarantee any minimum processing time for these background tasks.
A related problem with interrupt driven scheduling for network adapters is the potential for "livelock" situations. "Livelock" is a term coined to distinguish from "deadlock," which implies total paralysis of a processing system. A livelock can occur when there is so much received traffic that the adapter spends all of its time responding to interrupts generated as a result of received packets, and consequently there is insufficient time to deliver a packet to its destination before another interrupt occurs. In the event of a livelock, there is also no time to devote to background tasks.
One approach to avoiding livelocks is to disable interrupts until a received packet has been processed to completion. Partially completed work cannot be interrupted if this approach is used, but obviously this does nothing to improve the latency for a received packet. Background processing can be guaranteed using a similar approach, i.e. disabling interrupts periodically for a sufficient amount of time to process background tasks. The difficulty with this approach is in choosing an appropriate estimate of time for which to disable interrupts. If the estimate is too long, the adapter is unnecessarily prevented from performing one of its principal functions, which is to receive the next arriving packet. It would also exacerbate the latency. If the estimate is too short, there is no guarantee that the background tasks will be performed, because a subsequent interrupt for reception may occur.
It will be appreciated from the foregoing that there is still need for improvement in the way that network adapter operations are scheduled. The present invention satisfies this need.